/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package algo.graph;


import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import prefuse.data.tuple.TupleSet;
import prefuse.visual.EdgeItem;
import prefuse.visual.NodeItem;

/**
 *
 * @author krishen : Basé sur l'implementation de Lars Vogel
 */
public class DijkstraAlgorithm {

    private NodeItem nodeStart;
    //private NodeItem nodeEnd;

    private List<NodeItem> nodeItems;

    private Set<NodeItem> NoeudsTraitees;
    private Set<NodeItem> NoeudsNonTraitees;
    private Map<NodeItem, Integer> distance;
    private Map<NodeItem, NodeItem> predecesseurs;

    public DijkstraAlgorithm(NodeItem start){
        this.nodeStart =start;
        //this.nodeEnd = end;

   }

   /**
    * Debut du calcul
    */
    public void execute(){

        nodeItems = new ArrayList<NodeItem>();
        System.out.println("Dijkstraaaaaaaaaaaaaaa algo start");

        Object obj = null;
        NodeItem n = null;

        Iterator tuples = nodeStart.getGraph().tuples();
        while (tuples.hasNext() )
        {

            obj = tuples.next();
            if (obj instanceof prefuse.data.Node) { 
                n = (NodeItem) obj;
                //System.out.println("> Node : "+n.getString("name") );
                nodeItems.add(n);
            }
         }

        NoeudsTraitees = new HashSet<NodeItem>();
	NoeudsNonTraitees = new HashSet<NodeItem>();
	distance = new HashMap<NodeItem, Integer>();
	predecesseurs = new HashMap<NodeItem, NodeItem>();

        distance.put(nodeStart, 0);
	NoeudsNonTraitees.add(nodeStart);

       while (NoeudsNonTraitees.size() > 0){
            NodeItem node = getMinimum(NoeudsNonTraitees);
            NoeudsTraitees.add(node);
            NoeudsNonTraitees.remove(node);
            findMinimalDistances(node);

        }
    }

    /**
     *
     * @param node
     */
    private void findMinimalDistances(NodeItem node) {
		List<NodeItem> adjacentNodes = getNeighbors(node);
		for (NodeItem target : adjacentNodes) {
			if (getShortestDistance(target) > (getShortestDistance(node) + getDistance(node, target))  ) {
                            distance.put(target, getShortestDistance(node)+ getDistance(node, target));
			    predecesseurs.put(target, node);
			    NoeudsNonTraitees.add(target);
			}
		}

    }
    /**
     * Par defaut tout chemin renvoie une distance de 1
     * Ceci peut etre ammener a changer
     * @param node
     * @param target
     * @return 1
     */
    private int getDistance(NodeItem node, NodeItem target) {
        return 1;
    }


    /**
     *
     * @param vertex
     * @return
     */
    private boolean isSettled(NodeItem vertex) {
		return NoeudsTraitees.contains(vertex);
    }



    /**
     *
     * @param node
     * @return
     */
    private List<NodeItem> getNeighbors(NodeItem node) {
	List<NodeItem> neighbors = new ArrayList<NodeItem>();

         Iterator iter = node.edges();
        while ( iter.hasNext() ) {
            EdgeItem eitem = (EdgeItem)iter.next();
            NodeItem nitem = eitem.getAdjacentItem(node);

            if (!isSettled(nitem)){
                neighbors.add(nitem);

            }

        }
   	return neighbors;
    }




    /**
     * *
     * @param vertexes
     * @return
     */

    private NodeItem getMinimum(Set<NodeItem> vertexes) {
	NodeItem minimum = null;
	for (NodeItem vertex : vertexes) {
		if (minimum == null) {
			minimum = vertex;
		} else {
			if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
				minimum = vertex;
			}
		}
	}
	return minimum;
   }

    /**
     *
     * @param destination
     * @return
     */
    private int getShortestDistance(NodeItem destination) {
	Integer d = distance.get(destination);
	if (d == null) {
		return Integer.MAX_VALUE;
	} else {
		return d;
	}
    }

    /**
     *
     * @param target
     * @return
     */
    public LinkedList<NodeItem> getPath(NodeItem target) {
		LinkedList<NodeItem> path = new LinkedList<NodeItem>();
		NodeItem step = target;
		// Check if a path exists
		if (predecesseurs.get(step) == null) {
			return null;
		}
		path.add(step);
		while (predecesseurs.get(step) != null) {
			step = predecesseurs.get(step);
			path.add(step);
		}
		// Put it into the correct order
		Collections.reverse(path);
		return path;
	}


    /**
     * @return the vertexes
     */
    public List<NodeItem> getVertexes() {
        return nodeItems;
    }

    /**
     * @param vertexes the vertexes to set
     */
    public void setVertexes(List<NodeItem> nodeItems) {
        this.nodeItems = nodeItems;
    }


}
